//
// Description: 448. 找到所有数组中消失的数字
// Created by Loading on 2022/3/27.
//

#include <bits/stdc++.h>

using namespace std;

vector<int> findDisappearedNumbers(vector<int> &nums) {
    /* 数字对应在数组中的位置 + n，最后找到不大于 n 的元素位置即可 */
    vector<int> res;
    int n = nums.size();
    for (auto x : nums) {
        /* 注意：要还原原来的数字的下标 */
        int index = (x - 1) % n;
        nums[index] += n;
    }
    for (int i = 0; i < n; ++i) {
        if (nums[i] <= n) {
            res.emplace_back(i + 1);
        }
    }

    return res;
}

int main() {
    vector<int> nums{4, 3, 2, 7, 8, 2, 3, 1};
    auto res = findDisappearedNumbers(nums);
    for (auto x : res) {
        cout << x << ' ';
    }

    return 0;
}